The max-log-MAP decoding algorithm is a simplified version of the MAP decoding algorithm, which is also known as the BCJR decoding algorithm. The max-log-MAP is used to decode a convolutional encoder. It is one of the more popular soft output decoding methods.
A main application of the max-log-MAP decoder is in the decoding of turbo codes, which are generated using two parallel concatenated convolutional encoders. Two max-log-MAP decoders are used as component decoders in the turbo decoder. Today, turbo codes have become established as an important method of channel coding in the third generation wireless mobile communication technical specification. However, as time progresses and demand for high data rate communication increases, the turbo decoder is burdened with the task of performing with very high processing speed. Improving the speed of the component decoders of the turbo decoder, i.e. the max-log-MAP decoders, is the key to increasing turbo decoding speed.
The conventional max-log-MAP algorithm will now be described.
At the input of the max-log-MAP decoder are two kinds of received signals: received systematic symbols X and received coded symbols Y. A third possible kind of input signal is a lambda λ signal from the previous max-log-MAP decoder output if iterative decoding (turbo decoding) is applied. These signals are used to compute lambda, or in the case of turbo decoding, new lambda values. Several important internal signals of the max-log-MAP are defined: α, β, and Υ.
α and β are computed recursively—i.e. the computation of the internal signal α or β at a symbol sequence t needs the value of the internal signal from the previous, for α, or following, for β, symbol sequence (t−1 or t+1).
There are two types of Υ values: Υ0 is associated with the probability of a systematic symbol X being bit 0, while Υ1 is associated with the probability of the systematic symbol being bit 1. Υ is computed using X, Y and the lambda from the previous max-log-MAP decoder output, denoted by λp.
Signal Υ is calculated according to a trellis diagram. Table 1 gives and example of how Υ0 and Υ1, given states m, are calculated in an 8-state recursive systematic convolutional (RSC) encoder with the following transfer function: [1, g1(D)/g0(D)] where g0(D)=1+D2+D3 and g1=1+D+D3. In the above polynomials, the Ds describe a set of different Hamming distances (with respect to all zeros) that can be obtained from a convolutional encoder. Note that, 1 actually referes to D0 (Hamming distance of 0). Here, an 8-state RSC encoder is taken as an example. In fact, m can be other states, such as 16 states or 32 states, depending on the application.
TABLE 1Example of Υ values for states mmΥ0t(m)Υ1t(m)0−Yt − (Xt + λpt)+Yt + (Xt + λpt)1−Yt − (Xt + λpt)+Yt + (Xt + λpt)2+Yt − (Xt + λpt)−Yt + (Xt + λpt)3+Yt − (Xt + λpt)−Yt + (Xt + λpt)4+Yt − (Xt + λpt)−Yt + (Xt + λpt)5+Yt − (Xt + λpt)−Yt + (Xt + λpt)6−Yt − (Xt + λpt)+Yt + (Xt + λpt)7−Yt − (Xt + λpt)+Yt + (Xt + λpt)
The α for symbol sequence t and states m (total eight different states) is calculated using α and Υ at t−1 from two different states (m0 and m1). This is done by first computing an unnormalized signal ααt(m)=max-of-2{αt−1(m0)+Υ0t−1(m0), αt−1(m1)+Υ1t−1(m1)}  (1)
Using the example of the same RSC encoder used in Table 1, Table 2 gives the values of m0 and m1 corresponding to m, wherein states m0 and m1 are selected arbitrarily from eight different states m.
The initial values α0(m) are set to appropriate constants. Usually, α0(0) is set to 0 and {α0(1), α0(2), . . . , α0(7)} are set to a large negative number, for example, −128.
TABLE 2Example of m0 and m1 valuescorresponding to m for α computationMm0, m100, 113, 224, 537, 641, 052, 365, 476, 7
After all eight states are computed, all α values are normalized by subtracting a constant At.αt(m)=αt(m)−At  (2)At is a function of at αt which can be obtained in several ways. Some of them areAt=max-of-8{αt(m)}mε{0,1, . . . ,7}  (3a)At=(max-of-8{αt(m)}mε{0,1, . . . ,7}+min-of-8{αt(m)}mε{0,1, . . . ,7})/2  (3b)At=αt(0)  (3c)
Similarly, β is computed using information from different states (m0 and m1) and the symbol sequence t+1, and using Υ from states m at sequence t.
First, the unnormalized β is computedβt(m)=max-of-2{βt+1(m0)+Υ0t(m), βt+1(m1)+Υ1t(m)}  (4)
Table 3 gives the values of m0 and m1 corresponding to m, using the same RSC encoder.
The initial value βL+1(0), where L is the frame size, is usually set to 0, while {βL+1(1), βL+1(2), . . . , βL+1(7)} are usually set to a large negative number, for example, −128.
TABLE 3Example of m0 and m1 valuescorresponding to m for β computationmm0, m100, 414, 025, 131, 542, 656, 267, 373, 7
After all 8 states are computed, all β values are normalized by subtracting a constant Bt which is obtained in the similar way as Atβt(m)=βt(m)−Bt  (5)
Lambda is computed using α, β and Υ of all states. The m0 and m1 states for β are the same as given in Table 3.λt=max-of-8{αt(m)+Υ1t(m)+βt+1(m1)}mε{0,1 . . . ,7}−max-of-8{αt(m)+Υ0t(m)+βt+1(m0)}mε{0,1, . . . ,7}  (6)
As can be seen from the equations, two or more symbols of α or β cannot be computed in parallel, and therefore must be computed in sequence. However, the sequential computation of α can run in parallel with the sequential computation of β. Therefore, as α and β have exactly the same complexity and are independent of each other, from this point, the α and β computations are referred as a single entity called α/β computations, for convenience sake.
Lambda computations, however, are not independent of α/β computations. The lambda computation for symbol sequence t cannot begin until α and β of symbol sequence t are computed.
Looking at the algorithm for computing α/β for symbol sequence t (equations (1)–(5)), it can be seen that the algorithm can be divided into four dependent sequential stages. In other words, one stage cannot begin until the previous has been completed. For example, to compute α for symbol sequence t, the four stages S1(t)–S4(t) are    S1(t): Compute Υ0t−1(m0) and Υ1t−1(m1) using Table 1    S2(t): Compute αt(m) using equation (1)    S3(t): Compute At using one of the equations (3a), (3b), (3c)    S4(t): Compute αt(m) using equation (2)
It is possible to implement pipelining by starting S2 for the next symbol sequence t+1 after S4(t). This is because S1(t) is independent of any stage at any symbol sequence. FIG. 1 illustrates an example of the timeline of such an implementation, with the assumption that the length of time taken for the stages S1–S4 follows the proportion of T1:T2:T3:T4=1:1:1.5:0.5.
In general, the length of time taken to complete the stages given L number of symbols isT=T1+L(T2+T3+T4)  (7)
Using the prior art, the pipelining implementation is limited by the normalization computation (S3 and S4). In other words, part of the computation (referring to S2) of symbol sequence t+1 can begin only after the normalization computation in symbol sequence t is completed.
One way to improve this is to forgo the normalization computation for a few symbols (normalization can never be completely eliminated because it is needed to prevent overflow), but this would produce different results and slightly increase the number of bits which are set aside for the internal signals.
It is an object of the invention to provide a method of calculating decoding signals that can improve the pipelining implementation.